EVENTO
Análise Numérica de Métodos de Elementos Finitos Estabilizados para o Problema de Darcy
Tipo de evento: Seminário de Avaliação - Série A
Considere um grupo G, um conjunto X e uma fun¸cao f : G ! X tal que exista um subgrupoH de G, para o qual f(a) = f(b) se, e somente se, aH = bH quaisquer que sejam a, b 2 G. Oproblema de determinar um conjunto de geradores para H a partir de informa¸coes obtidas de f ´echamado o Problema do Subgrupo Escondido (PSE). Atualmente ele ´e um dos mais importantes eestudados problemas da Computa¸cao Quantica e ainda est´a longe de ser completamente resolvido.Muitos algoritmos quanticos que apresentam ganho exponencial em rela¸cao aos seus equivalentescl´assicos, como ´e o caso dos algoritmos de Shor[3] para a fatora¸cao e o c´alculo de logaritmo discreto,podem ser vistos como casos particulares de algoritmos quanticos para a solu¸cao do PSE; nosexemplos citados, o grupo G ´e abeliano e, neste caso, ´e conhecido um algoritmo quantico eficientepara a sua solu¸cao[4], enquanto nenhum algoritmo cl´assico eficiente o ´e. Um outro motivo para oesfor¸co de tentar resolver o PSE reside no fato de que, quando G ´e o grupo sim´etrico, sua solu¸caoimplica a solu¸cao do problema do isomorfismo de grafos, que possui aplica¸coes nas mais variadas´areas do conhecimento e para o qual nao se conhece nenhum algoritmo que o resolva eficientemente.Infelizmente, tamb´em nao se conhece nenhum algoritmo, nem cl´assico nem quantico, para a solu¸caodo PSE em Sn.Neste semin´ario apresentaremos o formalismo quantico para o PSE, mostrando as principaisferramentas usadas para o ataque ao problema, os casos onde o PSE est´a resolvido e tamb´em ondea pesquisa recente tem concentrado esfor¸co em sua solu¸cao.Referencias[1] Inui, Y. and Le Gall, F., An efficient quantum algorithm for the hidden subgroup problemover a class of semi-direct product groups, Los Alamos arXiv, quant-ph/0412033 v2, (2005)[2] Chi, D.P. and Kim, J.S. and Lee, S., Quantum algorithms for the hidden subgroup problem onsome semi-direct product groups by reduction to Abelian cases, Physics Letters A, vol. 359(2),pp. 114-116(2006)[3] Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on aquantum computer, SIAM Journal on Computing, vol. 26(5), pp. 14841509 (1997)[4] Mosca, M., Quantum Computer Algorithms, PhD thesis, University of Oxford, (1999)[5] Bacon, D. and Childs, A.M. and van Dam,W., From optimal measurement to efficient quantumalgorithms for the hidden subgroup problem over semi-direct product groups, Proceedings ofthe 2005 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS05),0-7695-2468-0/05 $20.00 IEEE (2005)
Data Início: 21/12/2005 Hora: 00:00 Data Fim: 21/12/2005 Hora: 00:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Maicon Ribeiro Correa - Universidade Estadual de Campinas - UNICAMP
Orientador: Abimael Fernando Dourado Loula - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Alexandre Loureiro Madureira - Laboratório Nacional de Computação Científica - LNCC Eduardo Gomes Dutra do Carmo - Universidade Federal do Rio de Janeiro - UFRJ Elson Magalhães Toledo - Laboratório Nacional de Computação Científica - LNCC Fernando A. Rochinha - PEM/COPPE - PEM/COPPE Marcio Arab Murad - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: João Nisan Correia Guerreiro - Laboratório Nacional de Computação Científica - LNCC Álvaro Coutinho - COPPE/UFRJ - COPPE/UFRJ
